The present invention generally relates to digital circuits, and, more particularly, to a binary adder and multiplier circuit.
With the advent of technologies that require complex and fast data processing, digital systems have evolved to more quickly perform mathematical operations. Since multiplication and addition are the most basic forms of mathematical operations performed by digital systems, different algorithms, such as the ripple-carry adder algorithm and Booth's multiplication algorithm, have been developed to reduce the time for a digital system to add and multiply two numbers.
The ripple-carry adder algorithm requires using multiple full-adders to add N-bit numbers. Each full adder is provided an intermediate sum generated by a previous full adder. Although the implementation of the ripple-carry adder is simple, which translates into low design time overhead, the ripple-carry adder is slow, since each full adder must wait for a carry bit to be calculated by the previous full adder.
Carry look ahead (CLA) adders have been developed to reduce computation time. CLA adders operate by creating two signals (P and G) for each bit position, based on whether a carry is propagated from a less significant bit position (at least one input is a binary one), generated in that bit position (both inputs are binary one), or eliminated in that bit position (both inputs are binary zero). In most cases, P is simply the sum output of a half-adder and G is a carry output of the same adder. After P and G are generated the carries for each bit position are created. CLA adders are fast and solve the shortcomings of ripple-carry adders. However, CLA adders require considerable additional logic to perform the pre-calculation of P and G, which impacts silicon area.
Booth's multiplication algorithm performs multiplication using shift and add operations. A conventional Booth's multiplier includes a multiplexer or mux, an accumulator, and a binary shifter. A first mux input receives the multiplicand and a second mux input receives binary zero. Bits of a multiplier are provided serially to a select input of the mux by right-shifting and providing the least significant bit (LSB) first. The mux output is provided to the accumulator. The multiplicand is added to a previous intermediate result stored in the accumulator for bits of the multiplier that are set to one and the result is right-shifted. The previous intermediate result is right-shifted, without the addition of the multiplicand, for the bits of the multiplier that are set to zero.
Since the intermediate result stored in the accumulator must be shifted for each bit of the multiplier, generating a final result requires a count of clock cycles equal to the bit-length of the multiplier, regardless of a value of the bit. Thus, 8 clock cycles are required for multiplying an 8-bit multiplier and multiplicand, and 16 clock cycles are required for multiplying a 16-bit multiplier and multiplicand. The number of clock cycles, and therefore the time required for multiplication increases in direct proportion to the bit-length of the multiplier, which limits the performance of the conventional Booth multiplier.
It would therefore be advantageous to have an adder and multiplier circuit that is fast, consumes fewer clock cycles and requires less logic, and that overcome the above-mentioned limitations of conventional adder and multiplier circuits.